<HTML><HEAD><TITLE>incremental_all_shortest_paths_as_edges(+Graph, +DistanceArg, +SourceNode, +Modified, -Lengths, -Predecessors)</TITLE>
</HEAD><BODY>[ <A HREF="index.html">library(graph_algorithms)</A> | <A HREF="../../index.html">Reference Manual</A> | <A HREF="../../fullindex.html">Alphabetic Index</A> ]
<H1>incremental_all_shortest_paths_as_edges(+Graph, +DistanceArg, +SourceNode, +Modified, -Lengths, -Predecessors)</H1>
Incrementally computes all shortest paths from a single source to every reachable node given a list of modified edges
<DL>
<DT><EM>Graph</EM></DT>
<DD>a graph structure
</DD>
<DT><EM>DistanceArg</EM></DT>
<DD>which argument of EdgeData to use as distance (integer)
</DD>
<DT><EM>SourceNode</EM></DT>
<DD>source node number (integer)
</DD>
<DT><EM>Modified</EM></DT>
<DD>list of e/3 edge structures whose DistanceArg argument has been modified
</DD>
<DT><EM>Lengths</EM></DT>
<DD>array of numbers (minimum path lengths)
</DD>
<DT><EM>Predecessors</EM></DT>
<DD>array of lists of e/3 edge structures
</DD>
</DL>
<H2>Description</H2>
<P>
    Incrementally computes all shortest paths from the single source
    node SourceNode to every sink node which is reachable from it
    given a list of modified edges. The result is returned in the form
    of the Predecessors array which contains all relevant edges.
</P><P>
    DistanceArg refers to the graph's EdgeData information that was
    specified when the graph was constructed. If EdgeData is a simple
    number, then DistanceArg should be 0 and EdgeData will be taken
    as the length of the edge. If EdgeData is a compound data structure,
    DistanceArg should be a number between 1 and the arity of that
    structure and determines which argument of the EdgeData structure
    will be interpreted as the edge's length. Important: the distance
    information in EdgeData must be a positive number.
</P><P>
    If DistanceArg is given as -1, then any EdgeData is ignored and
    the length of every edge is assumed to be equal to 1.
</P><P>
    SourceNode is the common starting point for the computed paths.
</P><P>
    Modified is the list of e/3 edge structures whose DistanceArg
    argument has been modified since the last computation for this
    SourceNode.
</P><P>
    The result is returned in the form of two arrays, whose indices range
    over the possible sink nodes.  The Lengths array indicates the length
    of a shortest path from SourceNode to the corresponding sink node.
    The Predecessors array is an array of edge lists, each list containing
    the alternative edges that are part of a shortest path from SourceNode
    to the corresponding sink node.
</P><P>
    If there is no path from SourceNode to a sink node J, then both
    Lengths[J] and Predecessors[J] are uninstantiated. Otherwise,
    Lengths[J] contains the length of a shortest path from SourceNode to J.
    Predecessors[J] contains a list of alternative edges that lead from
    some predecessor node to J in a shortest path from SourceNode to J.
    Predecessors[SourceNode] is always the empty list [].
</P>
<H4>Assembling Actual Paths</H4>
<P>
    To generate an actual path from the Predecessors array, start from the
    sink node J, select one of the alternative edges in Predecessors[J]
    to find a predecessor node, and continue this process until the SourceNode
    is reached. Depending on the parameters, the following 3 cases can occur:
    <OL>
    <LI>Graph did not contain zero-length edges: in this
    case, SubGraph is cycle-free and shortest paths can be found by simply
    selecting arbitrary incoming edges until SourceNode is reached.
    <LI>Graph did contain zero-length edges: in this case,
    SubGraph may contain (zero-length) cycles which one may want to exclude
    when constructing paths.
    </OL>
    The possible_path/7 predicate implements this path construction and
    does the necesssary checks to exclude cycles.
    </P>
<H3>Modes and Determinism</H3><UL>
<LI>incremental_all_shortest_paths_as_edges(+, +, +, +, -, -) is det
</UL>
<H2>Examples</H2>
<PRE>
    ?- sample_graph(G), incremental_all_shortest_paths_as_edges(G, 0, 1, M, L, E).
    L = [](0, 1, 2, 3, 2, 1, 1, _326, _327, 2, 3, 3, 3)
    E = []([], [e(1, 2, 1)], [e(7, 3, 1)], [e(5, 4, 1)],
	   [e(7, 5, 1), e(6, 5, 1)], [e(1, 6, 1)], [e(1, 7, 1)],
	   _342, _343, [e(7, 10, 1)], [e(10, 11, 1)], [e(10, 12, 1)],
	   [e(10, 13, 1)])
    </PRE>
<H2>See Also</H2>
<A HREF="../../lib/graph_algorithms/possible_path-7.html">possible_path / 7</A>, <A HREF="../../lib/graph_algorithms/shortest_paths-4.html">shortest_paths / 4</A>, <A HREF="../../lib/graph_algorithms/single_pair_shortest_path-5.html">single_pair_shortest_path / 5</A>, <A HREF="../../lib/graph_algorithms/all_short_paths_as_edges-6.html">all_short_paths_as_edges / 6</A>, <A HREF="../../lib/graph_algorithms/all_short_paths_as_graph-6.html">all_short_paths_as_graph / 6</A>, <A HREF="../../lib/graph_algorithms/incremental_all_shortest_paths_as_graph-6.html">incremental_all_shortest_paths_as_graph / 6</A>, <A HREF="../../lib/graph_algorithms/single_pair_short_path-6.html">single_pair_short_path / 6</A>, <A HREF="../../lib/graph_algorithms/single_pair_all_short_paths_as_graph-7.html">single_pair_all_short_paths_as_graph / 7</A>
</BODY></HTML>
